/*
 * This file is part of MonoSettlers.
 *
 * Copyright (C) 2010-2011 Christoph Husse
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Affero General Public License for more details.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Authors: 
 *      # Christoph Husse
 * 
 * Also checkout our homepage: http://opensettlers.codeplex.com/
 */
#ifndef PRIORITY_QUEUE_H_
#define PRIORITY_QUEUE_H_

#include <vector>

class CPriorityQueue
{
private:
	std::vector<LPPATHFINDER_NODE> InnerList;

	void SwitchElements(int i, int j)
	{
		LPPATHFINDER_NODE h = InnerList[i];
		InnerList[i] = InnerList[j];
		InnerList[j] = h;

		InnerList[i]->Index = i;
		InnerList[j]->Index = j;
	}

	int OnCompare(int i, int j)
	{
		const LPPATHFINDER_NODE a = InnerList[i];
		const LPPATHFINDER_NODE b = InnerList[j];

		if(a->F < b->F)
			return -1;
		else if(a->F > b->F)
			return 1;
		else
			return 0;
	}

public:

	~CPriorityQueue()
	{
		InnerList.~vector();
	}

	int Push(LPPATHFINDER_NODE item)
	{
		int p = InnerList.size(), p2;
		item->Index = InnerList.size();
		InnerList.push_back(item); // E[p] = O

		do
		{
			if (p == 0)
				break;
			p2 = (p - 1) / 2;
			if (OnCompare(p, p2) < 0)
			{
				SwitchElements(p, p2);
				p = p2;
			}
			else
				break;
		} while (true);
		return p;
	}

	/// <summary>
	/// Get the smallest object and remove it.
	/// </summary>
	/// <returns>The smallest object</returns>
	LPPATHFINDER_NODE Pop()
	{
		LPPATHFINDER_NODE result = InnerList[0];
		int p = 0, p1, p2, pn;

		InnerList[0] = InnerList[InnerList.size() - 1];
		InnerList[0]->Index = 0;

		InnerList.pop_back();

		result->Index = -1;

		do
		{
			pn = p;
			p1 = 2 * p + 1;
			p2 = 2 * p + 2;
			if (InnerList.size() > p1 && OnCompare(p, p1) > 0) // links kleiner
				p = p1;
			if (InnerList.size() > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
				p = p2;

			if (p == pn)
				break;
			SwitchElements(p, pn);
		} while (true);

		return result;
	}

	/// <summary>
	/// Notify the PQ that the object at position i has changed
	/// and the PQ needs to restore order.
	/// </summary>
	void Update(LPPATHFINDER_NODE item)
	{
		int count = InnerList.size();

		// usually we only need to switch some elements, since estimation won't change that much.
		while ((item->Index - 1 >= 0) && (OnCompare(item->Index - 1, item->Index) > 0))
		{
			SwitchElements(item->Index - 1, item->Index);
		}

		while ((item->Index + 1 < count) && (OnCompare(item->Index + 1, item->Index) < 0))
		{
			SwitchElements(item->Index + 1, item->Index);
		}
	}

	/// <summary>
	/// Get the smallest object without removing it.
	/// </summary>
	/// <returns>The smallest object</returns>
	LPPATHFINDER_NODE Peek()
	{
		if (InnerList.size() > 0)
			return InnerList[0];
		return NULL;
	}

	void Clear()
	{
		InnerList.clear();
	}

	int Count()
	{
		return InnerList.size();
	}
};

#endif